InforLorV4, Main, Exploration, bibRecord, 009F00

Enumeration of Planar Constellations

Identifieur interne : 009F00 ( Main/Exploration ); précédent : 009E99; suivant : 009F01

Enumeration of Planar Constellations

Auteurs : Mireille Bousquet-Mélou [France] ; Gilles Schaeffer [France]

Source :

Advances in Applied Mathematics [ 0196-8858 ] ; 2000.

RBID : ISTEX:3AA8B260A25479256212C70DB6B06DA6F9A27FF5

English descriptors

Teeft :
- Acts transitively, Balanced eulerian tree, Balanced eulerian trees, Balanced tree, Balanced trees, Bijection, Black leaf, Cactus, Canonical labelling, Characteristic formula, Conjugacy class, Conjugacy classes, Constellation, Counterclockwise, Counterclockwise order, Different ways, Distinct points, Enumeration, Eulerian, Eulerian maps, Eulerian trees, Extra star, Factorization, Hurwitz, Inner degree, Inner edge, Inner vertices, Minimal transitive factorizations, Nite face, Other words, Permutation, Planar, Planar constellations, Planar maps, Plane trees, Polygon, Rank forest, Resp, Riemann surfaces, Right vertex, Root edge, Root polygon, Same tree, Schaeffer, Special edge, Such trees, Symmetric group, Total degree, Transitive, Transitively, Transitivity condition, Transposition, Unrooted, Unrooted constellations, Vertex, White face, White leaf, White vertices.
mix :
- bijection, cartes planaires, conjugaison d'arbres, conjugation of trees, coverings, hurwitz, maps, revêtements, tutte.

Abstract

Abstract: The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let n≥1, and let σ0 be a permutation of Sn having di cycles of length i, for i≥1. Let m≥2. We prove that the number of m-tuples (σ1,…,σm) of permutation of Sn such that • σσ···σ=σ, • the group generated by σ,…,σ acts transitively on {1,2,…,}, • ∑(σ)=(−1)+2, where (σ) denotes the number of cycles of σ A one-to-one correspondence relates these m-tuples to some rooted planar maps, which we call constellations and enumerate via a bijection with some bicolored trees. For m=2, we recover a formula of Tutte for the number of Eulerian maps. The proof relies on the idea that maps are conjugacy classes of trees and extends the method previously applied to Eulerian maps by the second author. Our result might remind the reader of an old theorem of Hurwitz, giving the number of m-tuples of transpositions satisfying the above conditions. Indeed, we show that our result implies Hurwitz' theorem. We also briefly discuss its implications for the enumeration of nonequivalent coverings of the sphere.

Url:

DOI: 10.1006/aama.1999.0673

Affiliations:

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Enumeration of Planar Constellations</title>
<author><name sortKey="Bousquet Melou, Mireille" sort="Bousquet Melou, Mireille" uniqKey="Bousquet Melou M" first="Mireille" last="Bousquet-Mélou">Mireille Bousquet-Mélou</name>
</author>
<author><name sortKey="Schaeffer, Gilles" sort="Schaeffer, Gilles" uniqKey="Schaeffer G" first="Gilles" last="Schaeffer">Gilles Schaeffer</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:3AA8B260A25479256212C70DB6B06DA6F9A27FF5</idno>
<date when="2000" year="2000">2000</date>
<idno type="doi">10.1006/aama.1999.0673</idno>
<idno type="url">https://api.istex.fr/ark:/67375/6H6-ZC4L6S7D-R/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000D83</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000D83</idno>
<idno type="wicri:Area/Istex/Curation">000D73</idno>
<idno type="wicri:Area/Istex/Checkpoint">002153</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">002153</idno>
<idno type="wicri:doubleKey">0196-8858:2000:Bousquet Melou M:enumeration:of:planar</idno>
<idno type="wicri:Area/Main/Merge">00A481</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:inria-00099358</idno>
<idno type="url">https://hal.inria.fr/inria-00099358</idno>
<idno type="wicri:Area/Hal/Corpus">001F93</idno>
<idno type="wicri:Area/Hal/Curation">001F93</idno>
<idno type="wicri:Area/Hal/Checkpoint">006263</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">006263</idno>
<idno type="wicri:doubleKey">0196-8858:2000:Bousquet Melou M:enumeration:of:planar</idno>
<idno type="wicri:Area/Main/Merge">00A894</idno>
<idno type="wicri:Area/Main/Curation">009F00</idno>
<idno type="wicri:Area/Main/Exploration">009F00</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Enumeration of Planar Constellations</title>
<author><name sortKey="Bousquet Melou, Mireille" sort="Bousquet Melou, Mireille" uniqKey="Bousquet Melou M" first="Mireille" last="Bousquet-Mélou">Mireille Bousquet-Mélou</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405, Talence Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Nouvelle-Aquitaine</region>
<region type="old region" nuts="2">Aquitaine</region>
<settlement type="city">Talence</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Schaeffer, Gilles" sort="Schaeffer, Gilles" uniqKey="Schaeffer G" first="Gilles" last="Schaeffer">Gilles Schaeffer</name>
<affiliation wicri:level="3"><country xml:lang="fr">France</country>
<wicri:regionArea>CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405, Talence Cedex</wicri:regionArea>
<placeName><region type="region" nuts="2">Nouvelle-Aquitaine</region>
<region type="old region" nuts="2">Aquitaine</region>
<settlement type="city">Talence</settlement>
</placeName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="j">Advances in Applied Mathematics</title>
<title level="j" type="abbrev">YAAMA</title>
<idno type="ISSN">0196-8858</idno>
<imprint><publisher>ELSEVIER</publisher>
<date type="published" when="2000">2000</date>
<biblScope unit="volume">24</biblScope>
<biblScope unit="issue">4</biblScope>
<biblScope unit="page" from="337">337</biblScope>
<biblScope unit="page" to="368">368</biblScope>
</imprint>
<idno type="ISSN">0196-8858</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0196-8858</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Acts transitively</term>
<term>Balanced eulerian tree</term>
<term>Balanced eulerian trees</term>
<term>Balanced tree</term>
<term>Balanced trees</term>
<term>Bijection</term>
<term>Black leaf</term>
<term>Cactus</term>
<term>Canonical labelling</term>
<term>Characteristic formula</term>
<term>Conjugacy class</term>
<term>Conjugacy classes</term>
<term>Constellation</term>
<term>Counterclockwise</term>
<term>Counterclockwise order</term>
<term>Different ways</term>
<term>Distinct points</term>
<term>Enumeration</term>
<term>Eulerian</term>
<term>Eulerian maps</term>
<term>Eulerian trees</term>
<term>Extra star</term>
<term>Factorization</term>
<term>Hurwitz</term>
<term>Inner degree</term>
<term>Inner edge</term>
<term>Inner vertices</term>
<term>Minimal transitive factorizations</term>
<term>Nite face</term>
<term>Other words</term>
<term>Permutation</term>
<term>Planar</term>
<term>Planar constellations</term>
<term>Planar maps</term>
<term>Plane trees</term>
<term>Polygon</term>
<term>Rank forest</term>
<term>Resp</term>
<term>Riemann surfaces</term>
<term>Right vertex</term>
<term>Root edge</term>
<term>Root polygon</term>
<term>Same tree</term>
<term>Schaeffer</term>
<term>Special edge</term>
<term>Such trees</term>
<term>Symmetric group</term>
<term>Total degree</term>
<term>Transitive</term>
<term>Transitively</term>
<term>Transitivity condition</term>
<term>Transposition</term>
<term>Unrooted</term>
<term>Unrooted constellations</term>
<term>Vertex</term>
<term>White face</term>
<term>White leaf</term>
<term>White vertices</term>
</keywords>
<keywords scheme="mix" xml:lang="en"><term>bijection</term>
<term>cartes planaires</term>
<term>conjugaison d'arbres</term>
<term>conjugation of trees</term>
<term>coverings</term>
<term>hurwitz</term>
<term>maps</term>
<term>revêtements</term>
<term>tutte</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: The enumeration of transitive ordered factorizations of a given permutation is a combinatorial problem related to singularity theory. Let n≥1, and let σ0 be a permutation of Sn having di cycles of length i, for i≥1. Let m≥2. We prove that the number of m-tuples (σ1,…,σm) of permutation of Sn such that • σσ···σ=σ, • the group generated by σ,…,σ acts transitively on {1,2,…,}, • ∑(σ)=(−1)+2, where (σ) denotes the number of cycles of σ A one-to-one correspondence relates these m-tuples to some rooted planar maps, which we call constellations and enumerate via a bijection with some bicolored trees. For m=2, we recover a formula of Tutte for the number of Eulerian maps. The proof relies on the idea that maps are conjugacy classes of trees and extends the method previously applied to Eulerian maps by the second author. Our result might remind the reader of an old theorem of Hurwitz, giving the number of m-tuples of transpositions satisfying the above conditions. Indeed, we show that our result implies Hurwitz' theorem. We also briefly discuss its implications for the enumeration of nonequivalent coverings of the sphere.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Aquitaine</li>
<li>Nouvelle-Aquitaine</li>
</region>
<settlement><li>Talence</li>
</settlement>
</list>
<tree><country name="France"><region name="Nouvelle-Aquitaine"><name sortKey="Bousquet Melou, Mireille" sort="Bousquet Melou, Mireille" uniqKey="Bousquet Melou M" first="Mireille" last="Bousquet-Mélou">Mireille Bousquet-Mélou</name>
</region>
<name sortKey="Schaeffer, Gilles" sort="Schaeffer, Gilles" uniqKey="Schaeffer G" first="Gilles" last="Schaeffer">Gilles Schaeffer</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 009F00 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 009F00 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:3AA8B260A25479256212C70DB6B06DA6F9A27FF5
   |texte=   Enumeration of Planar Constellations
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

Serveur d'exploration sur la recherche en informatique en Lorraine

Enumeration of Planar Constellations

Enumeration of Planar Constellations

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.